In a large-scale computer system, it is important to operate the entire system efficiently. In general, a job scheduler allocates a node to the job for executing the job in consideration of time and spatial factors. The job is executed by the allocated node. The job scheduler is software configured to manage the job to be executed by the computer system. For example, the job scheduler also controls start and end of a plurality of jobs (program and batch processing), as well as monitors and reports job's execution and end state, in addition to the allocation of the node to the job.
When allocating a plurality of nodes to the job, adjoining nodes are allocated as much as possible for efficient communication between nodes executing the job. For example, if the system has a network topology of a mesh or torus connection, a sub-mesh (a rectangular area in the case of a two dimensional structure, or a cuboid area in the case of a three dimensional structure) is established within the network. Then, a free node in the sub-mesh is allocated to one job. The free node is a node not executing the job.
However, even if the network as a whole has free nodes corresponding to the number of nodes used for execution of the job, there may be a case where it is difficult to secure a sub-mesh including nodes corresponding to the number of nodes. One of the factors therefor may be that free nodes are in a fragmentation state. The fragmentation state is a state where a node in use and a free node are located in a worm-eaten state. For example, the system becomes in the fragmentation state due to an erroneous estimate of the job execution completion time during the transition of time. The fragmentation state lowers operation efficiency of the system and thereby deteriorates the throughput.
As a technique for improving the use efficiency of the job, for example, there is a technique which predicts a system operating state after elapse of a predetermined time based on measurement data and analysis data and establishes an optimum job execution environment based on the prediction result. Also, there is a technique which reduces a scheduling error caused by job execution and thereby improves the utilization efficiency of the computer resources in the parallel computing system. Further, a technique for suppressing violent fluctuation of the response time has also been studied.
Related techniques are disclosed in, for example, Japanese Laid-open Patent Publication Nos. 7-219787, 2002-007364, and 2014-049112.
When a well-arranged free node group is not found due to the fragmentation of free nodes, the well-arranged free node group may be generated, for example, by the job migration. The job migration is a technique which moves a job being executed by a node to another node. To generate a well-arranged free node group by the job migration, free nodes which may resolve the fragmentation are searched for as the migration destination of the job.
In the case of a large-scale system, however, if the migration destination of the job is searched for throughout the system, an extensive range is searched. For example, when searching for locations for relevant jobs simply based on an optimum solution as a whole, there are a huge number of combinations which take enormous time for computation. Thus, there is a problem in that it is difficult to perform the processing in real time.
According to an aspect of the present disclosure, an object of the embodiments is to quickly provide a well-arranged free node group.